{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Difference LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个整数数组<code>a</code>和<code>b</code>，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}\n",
    "<strong>输出：</strong>3，即数值对(11, 8)\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= a.length, b.length <= 100000</code></li>\n",
    "\t<li><code>-2147483648 <= a[i], b[i] <= 2147483647</code></li>\n",
    "\t<li>正确结果在区间 <code>[0, 2147483647]</code> 内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-difference-lcci](https://leetcode.cn/problems/smallest-difference-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-difference-lcci](https://leetcode.cn/problems/smallest-difference-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0]\\n[2147483647]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        ans = inf\n",
    "        m, n = len(a), len(b)\n",
    "        i = j = 0\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        while i < m and j < n:\n",
    "            d = abs(a[i] - b[j])\n",
    "            ans = min(ans, d)\n",
    "            if a[i] > b[j]:\n",
    "                j += 1\n",
    "            elif a[i] < b[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                return 0\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        i = j = 0\n",
    "        ans = 2147483647*2\n",
    "        while i<len(a) and j<len(b):\n",
    "            ans = min(ans,abs(a[i]-b[j]))\n",
    "            if a[i] < b[j]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        i,j=0,0\n",
    "        ret=float(\"inf\")\n",
    "        while i<len(a) and j<len(b):\n",
    "            ret=min(ret,abs(a[i]-b[j]))\n",
    "            if a[i]<b[j]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        ans = 2**32\n",
    "        i,j = 0,0\n",
    "        while i<len(a) and j <len(b):\n",
    "            ans = min(ans,abs(b[j]-a[i]))\n",
    "            if a[i]>b[j]:\n",
    "                j+=1\n",
    "            elif a[i]<b[j]:\n",
    "                i+=1\n",
    "            else:\n",
    "                return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        ans = inf\n",
    "        i = j = 0\n",
    "        n, m = len(a), len(b)\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        while i < n and j < m:\n",
    "            if a[i] < b[j]:\n",
    "                ans = min(ans, b[j] - a[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                ans = min(ans, a[i] - b[j])\n",
    "                j += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        ans = inf\n",
    "        p1 = p2 = 0\n",
    "        while p1 < len(a) and p2 < len(b):\n",
    "            ans = min(ans, abs(a[p1] - b[p2]))\n",
    "            if a[p1] <= b[p2]: p1 += 1\n",
    "            else: p2 += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "\n",
    "        ans = float('inf')\n",
    "        i,j = 0,0\n",
    "        while i<len(a) and j<len(b):\n",
    "            ans = min(ans, abs(a[i] - b[j]))\n",
    "            if a[i]>b[j]:\n",
    "                j += 1\n",
    "            elif a[i] < b[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                return 0\n",
    "        return ans\n",
    "\n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        print(a,b)\n",
    "        if b[0] < a[0]:\n",
    "            a,b = b,a\n",
    "        # 差绝对值最小是0，所以碰到0可以直接返回。其他情况则记录+比较\n",
    "        min_abs = abs(a[0]-b[0])\n",
    "        # if b[0] > a[-1]:\n",
    "        #     return b[0]-a[-1]\n",
    "        i = j = 0\n",
    "        while i < len(a) and j < len(b):\n",
    "            if abs(a[i] - b[j]) == 0:\n",
    "                return 0\n",
    "            min_abs = min(min_abs, abs(a[i] - b[j]))\n",
    "            if b[j] > a[i]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return min_abs\n",
    "\n",
    "        return min_abs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        a.sort()\n",
    "     \n",
    "        mn = inf\n",
    "    \n",
    "        for b_ in b:\n",
    "        \n",
    "            i = bisect_left(a, b_)\n",
    "            \n",
    "            mn = min(mn, abs(b_-a[i]) if i < len(a) else inf, abs(b_-a[i-1]) if i >= 1 else inf)\n",
    "           \n",
    "        return mn \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        new_a = list(set(a))\n",
    "        new_a.sort()\n",
    "        new_b = list(set(b))\n",
    "        ans = float('inf')\n",
    "        for x in new_b:\n",
    "            p = bisect.bisect_left(new_a, x)\n",
    "            if p == len(new_a):\n",
    "                ans = min(ans, abs(x - new_a[p-1]))\n",
    "            else:\n",
    "                ans = min(ans, abs(x - new_a[p]))\n",
    "                if p > 0:\n",
    "                    ans = min(ans, abs(x - new_a[p-1]))\n",
    "            if ans == 0: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        sa, sb = sorted(a), sorted(b)\n",
    "        ans = inf\n",
    "        i, j = 0, 0\n",
    "        print(sa, sb)\n",
    "        while i < len(sa) and j < len(sb):\n",
    "            ans = min(abs(sa[i] - sb[j]), ans)\n",
    "            if sa[i] < sb[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        m,n=len(a),len(b)\n",
    "        i,j=0,0\n",
    "        ans=[]\n",
    "        while i<m and j<n:\n",
    "            ans.append(abs(a[i]-b[j]))\n",
    "            if a[i]<b[j]:\n",
    "                i+=1\n",
    "            else:\n",
    "                j+=1\n",
    "        if i==m:\n",
    "            tmp=[abs(a[m-1]-b[k]) for k in range(j+1,n)]\n",
    "            ans=ans+tmp\n",
    "        elif j==n:\n",
    "            tmp=[abs(a[k]-b[n-1]) for k in range(i+1,m)]\n",
    "            ans=ans+tmp\n",
    "        return min(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int: \n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        \n",
    "        if b[0] >= a[-1]:\n",
    "            return abs(b[0]-a[-1])\n",
    "        elif a[0] > b[-1]:\n",
    "            return abs(a[0]-b[-1])\n",
    "\n",
    "        min_ = []\n",
    "        n = 0\n",
    "        bigflag = None\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            minflag = None\n",
    "            flag = 0\n",
    "            for j in range(n, len(b)):\n",
    "                if b[j] == a[i]:\n",
    "                    return 0\n",
    "                elif b[j] > a[i]:\n",
    "                    n = j\n",
    "                    bigflag = 1\n",
    "                    if minflag:\n",
    "                        min_.append(min(abs(b[j] - a[i]), abs(a[i] - b[j-1])))\n",
    "                    break\n",
    "                else:\n",
    "                    minflag = 1\n",
    "                    if bigflag:\n",
    "                        min_.append(min(abs(a[i] - b[j]), abs(b[j] - a[i-1])))\n",
    "                    continue\n",
    "        return min(min_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        # 方法2: 排序后二分+剪枝\n",
    "        # 优化1 - 去重\n",
    "        a = list(set(a))\n",
    "        b = list(set(b))\n",
    "        if len(a) < len(b):\n",
    "            # 优化2 - 排序较短的数组\n",
    "            return self.smallestDifference(b, a)\n",
    "        b.sort()\n",
    "        res = float(\"inf\")\n",
    "        for x in a:\n",
    "            # 注意这里使用bisect, 这样查找到的j是首个大于x的下标, 只需要判断j-1和j即可\n",
    "            j = bisect.bisect(b, x)\n",
    "            for k in (j - 1, j):\n",
    "                if 0 <= k < len(b):\n",
    "                    res = min(res, abs(x - b[k]))\n",
    "                    if res == 0:\n",
    "                        # 优化3 - 差为0时直接返回, 不可能有更小的差\n",
    "                        return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int: \n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        \n",
    "        if b[0] >= a[-1]:\n",
    "            return abs(b[0]-a[-1])\n",
    "        elif a[0] > b[-1]:\n",
    "            return abs(a[0]-b[-1])\n",
    "\n",
    "        min_ = []\n",
    "        n = 0\n",
    "        bigflag = None\n",
    "        \n",
    "        for i in range(len(a)):\n",
    "            minflag = None\n",
    "            flag = 0\n",
    "            for j in range(n, len(b)):\n",
    "                if b[j] == a[i]:\n",
    "                    return 0\n",
    "                elif b[j] > a[i]:\n",
    "                    n = j\n",
    "                    bigflag = 1\n",
    "                    if minflag:\n",
    "                        min_.append(min(abs(b[j] - a[i]), abs(a[i] - b[j-1])))\n",
    "                    break\n",
    "                else:\n",
    "                    minflag = 1\n",
    "                    if bigflag:\n",
    "                        min_.append(min(abs(a[i] - b[j]), abs(b[j] - a[i-1])))\n",
    "                    continue\n",
    "        return min(min_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        total=a+b\n",
    "        total.sort()\n",
    "        aset=set(a)\n",
    "        bset=set(b)\n",
    "        gap=total[-1]-total[0]\n",
    "        counta=0\n",
    "        N=len(a)\n",
    "        for i in range(len(total)-1):\n",
    "            diff=total[i+1]-total[i]\n",
    "            if diff==0 and total[i] in aset and total[i] in bset:\n",
    "                return 0\n",
    "            if ((total[i+1] in aset and total[i] not in aset) or(total[i] in aset and total[i+1] not in aset)) and diff<gap:\n",
    "                # if diff<gap:\n",
    "                gap=diff\n",
    "            if total[i] in aset:\n",
    "                counta+=1\n",
    "                if counta==N:\n",
    "                    return gap\n",
    "        return gap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        arr = []\n",
    "        for i in a:\n",
    "            arr.append((i, \"a\"))\n",
    "        for j in b:\n",
    "            arr.append((j, \"b\"))\n",
    "        arr = sorted(arr)\n",
    "        Min = abs(a[0]-b[0])\n",
    "        i, j = 0, 1\n",
    "        # print(arr)\n",
    "        while j < len(arr):\n",
    "            if arr[i][1] != arr[j][1] and abs(arr[i][0] - arr[j][0]) < Min:\n",
    "                Min = abs(arr[i][0]-arr[j][0])\n",
    "            j += 1\n",
    "            i += 1\n",
    "        return Min\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        unionList = list(zip(a + b, [0] * len(a) + [1] * len(b)))\n",
    "        #将两个数组混合按大小排序\n",
    "        unionList.sort(key=self.getElement0)\n",
    "        lasta, lastb, minD = None, None, 2147483647\n",
    "        #获取跟另一个数组的最小差值\n",
    "        for num in unionList:\n",
    "            if num[1] == 0:\n",
    "                lasta = num[0]\n",
    "                if lastb is not None:\n",
    "                    minD = min(minD, abs(lastb - lasta))\n",
    "            elif num[1] == 1:\n",
    "                lastb = num[0]\n",
    "                if lasta is not None:\n",
    "                    minD = min(minD, abs(lastb - lasta))\n",
    "        return minD\n",
    "    \n",
    "    def getElement0(self, ele):\n",
    "        return ele[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a,b):\n",
    "    t=[(e,0) for e in a]+[(e,1) for e in b]\n",
    "    t.sort(key=lambda x:x[0])\n",
    "    m=abs(a[0]-b[0])\n",
    "    for i in range(len(t)-1):\n",
    "        if t[i][1]!=t[i+1][1]:\n",
    "            m=min(m,t[i+1][0]-t[i][0])\n",
    "            if not m:\n",
    "                return 0\n",
    "    return m\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        return f(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        v= [(aa,1) for aa in a]+[(bb,-1) for bb in b]\n",
    "        v.sort(key=lambda x:x[0])\n",
    "        ans = 2147483647\n",
    "        for i in range(1,len(v)):\n",
    "            if v[i][1]*v[i-1][1] < 0:\n",
    "                ans = min(ans,abs(v[i][0]-v[i-1][0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        numsIndexSorted = [i for i in range(len(a) + len(b))]\n",
    "        def f(index: int):\n",
    "            return a[index] if index < len(a) else b[index-len(a)]\n",
    "        numsIndexSorted.sort(key = f)\n",
    "\n",
    "        res = abs(a[0]-b[0])\n",
    "        for i in range(len(numsIndexSorted)-1):\n",
    "            if (numsIndexSorted[i] < len(a)) ^ (numsIndexSorted[i+1] < len(a)):\n",
    "                diff = abs(f(numsIndexSorted[i]) - f(numsIndexSorted[i+1]))\n",
    "                res = min(diff, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "\n",
    "        nums,index=[],[]\n",
    "        i,j=0,0\n",
    "\n",
    "        while i<len(a) or j<len(b):\n",
    "            if i==len(a):\n",
    "                nums+=b[j:]\n",
    "                l2=len(b[j:])\n",
    "                index+=[2 for i in range(l2)]\n",
    "                break\n",
    "            elif j==len(b):\n",
    "                nums+=a[i:]\n",
    "                l1=len(a[i:])\n",
    "                index+=[1 for i in range(l1)]\n",
    "                break\n",
    "            elif a[i]<b[j]:\n",
    "                nums.append(a[i])\n",
    "                index.append(1)\n",
    "                i+=1\n",
    "            else:\n",
    "                nums.append(b[j])\n",
    "                index.append(2)\n",
    "                j+=1\n",
    "\n",
    "        ans=inf\n",
    "        for i in range(1,len(index)):\n",
    "            if index[i]!=index[i-1]:\n",
    "                ans=min(ans,nums[i]-nums[i-1])\n",
    "\n",
    "        return ans\n",
    "                          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        l1, l2 = len(a), len(b)\n",
    "        i, j = 0, 0 \n",
    "        if a[0] >= b[-1] or b[0] >= a[-1]:\n",
    "            return min(abs(a[0] - b[-1]), abs(a[-1] - b[0]))\n",
    "        res = []\n",
    "        while i < l1 and j < l2:\n",
    "            res.append(abs(a[i] - b[j]))\n",
    "            if a[i] > b[j]:\n",
    "                j += 1 \n",
    "            else:\n",
    "                i += 1 \n",
    "        \n",
    "        if i == l1:\n",
    "            tmp = [abs(a[-1] - b[k]) for k in range(j + 1, l2)]\n",
    "        if j == l2:\n",
    "            tmp = [abs(b[-1] - a[k]) for k in range(i + 1, l1)]\n",
    "        res.extend(tmp)\n",
    "        return min(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        res = float('inf')\n",
    "        ab = a + b\n",
    "        ab.sort()\n",
    "        a_set = set(a)\n",
    "        b_set = set(b)\n",
    "        left = 0\n",
    "        for right in range(1, len(ab)):\n",
    "            num = abs(ab[left] - ab[right])\n",
    "            if num < res:\n",
    "                if (ab[left] in a_set and ab[right] in b_set) or (\n",
    "                        ab[left] in b_set and ab[right] in a_set):\n",
    "                    res = num\n",
    "            left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        list_ = []\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        while len(a) >= 1 and len(b) >= 1:\n",
    "            if a[-1] > b[-1]:\n",
    "                list_.append((a.pop(), 1))\n",
    "            else:\n",
    "                list_.append((b.pop(), -1))\n",
    "        list_.extend(reversed(list(zip(a, [1] * len(a)))))\n",
    "        list_.extend(reversed(list(zip(b, [-1] * len(b)))))\n",
    "        min_number = 2147483647\n",
    "        for i in range(len(list_) - 1):\n",
    "            if list_[i + 1][1] + list_[i][1] == 0:\n",
    "                min_number = min(min_number, abs(list_[i + 1][0] - list_[i][0]))\n",
    "        return min_number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 大道至简，把a和b拼起来后进行排序\n",
    "# 从左到右来一遍，记录差的最小值(做差的两元素应该分别来自a和b)\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a_set=set(a)\n",
    "        b_set=set(b)\n",
    "        ab=sorted(a+b)\n",
    "        n=len(ab)\n",
    "        ret=1e10\n",
    "        for i in range(n-1):\n",
    "            if (ab[i] in a_set and ab[i+1] in b_set) or\\\n",
    "                (ab[i] in b_set and ab[i+1] in a_set):\n",
    "                    ret=min(ret,ab[i+1]-ab[i])\n",
    "        return ret            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        # start 1340\n",
    "        # debug 1354\n",
    "        if not a or not b: return None\n",
    "        li = [(x, 0) for x in a] + [(y, 1) for y in b]\n",
    "        li.sort()\n",
    "        l = len(li)\n",
    "\n",
    "        res = li[-1][0] - li[0][0]\n",
    "\n",
    "        def scan(target):\n",
    "            nonlocal res\n",
    "            # gap begin with target\n",
    "            i = 0\n",
    "            while i < l and li[i][1] == 1-target: \n",
    "                i += 1\n",
    "            j = i + 1\n",
    "            # scan \n",
    "            while j < l:\n",
    "                if li[j][1] == 1-target:\n",
    "                    res = min(res, li[j][0]-li[i][0])\n",
    "                else:\n",
    "                    i = j\n",
    "                j += 1\n",
    "\n",
    "        scan(0)\n",
    "        scan(1)\n",
    "\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a = sorted(list(set(a)))\n",
    "        b = list(set(b))\n",
    "        mn = inf\n",
    "        for x in b:\n",
    "            j = bisect_left(a, x)\n",
    "            if j == len(a):\n",
    "                mn = min(mn, abs(x - a[-1]))\n",
    "            else:\n",
    "                mn = min(mn, abs(a[j] - x), abs(x - a[j - 1]))\n",
    "            if mn == 0:\n",
    "                return 0\n",
    "        return mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        looked1={}\n",
    "        looked2={}\n",
    "        for one in a:\n",
    "            if one not in looked1:\n",
    "                looked1[one]=1\n",
    "        for one in b:\n",
    "            if one not in looked2:\n",
    "                looked2[one]=1\n",
    "        hebing=a.copy()\n",
    "        hebing.extend(b)\n",
    "        hebing.sort()\n",
    "        nowmin=2147483648\n",
    "        for i in range(1,len(hebing)):\n",
    "            jieguo=abs(hebing[i]-hebing[i-1])\n",
    "            if jieguo<nowmin:\n",
    "                if (hebing[i] in looked1 and hebing[i-1]in looked2) or \\\n",
    "                    (hebing[i] in looked2 and hebing[i-1] in looked1):\n",
    "                    nowmin=jieguo\n",
    "                    if nowmin==0:\n",
    "                        return 0\n",
    "        return nowmin\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a = [(i,'a') for i in a]\n",
    "        b = [(i,'b') for i in b]\n",
    "        s = a + b \n",
    "        s.sort()\n",
    "        res = float('inf')\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i][1] != s[i-1][1]:\n",
    "                res =  min(res,abs(s[i][0]-s[i-1][0]))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        list_ = sorted([(x, 1) for x in a] + [(x, -1) for x in b])\n",
    "        min_number = 2147483647\n",
    "        for i in range(len(list_) - 1):\n",
    "            if list_[i + 1][1] + list_[i][1] == 0:\n",
    "                min_number = min(min_number, abs(list_[i + 1][0] - list_[i][0]))\n",
    "        return min_number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        s = sorted(itertools.chain(((n,0) for n in a), ((n, 1) for n in b)))\n",
    "        result = float('inf')\n",
    "        for (n1, id1), (n2, id2) in zip(s, s[1:]):\n",
    "            if id1 != id2:\n",
    "                result = min(result, n2-n1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        c = []\n",
    "        for x in a:\n",
    "            c.append((x, 1))\n",
    "        for x in b:\n",
    "            c.append((x, 2))\n",
    "        c.sort(key=lambda x:x[0])\n",
    "        diff = float(inf)\n",
    "        ct = c[0][1]\n",
    "        current = c[0][0]\n",
    "        for x, t in c[1:]:\n",
    "            if t == ct:\n",
    "                current = x\n",
    "            else:\n",
    "                diff = min(diff, x - current)\n",
    "                current = x\n",
    "                ct = t\n",
    "        return diff\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        temp = []\n",
    "        for element in a:\n",
    "            temp.append((element, 0))\n",
    "        for element in b:\n",
    "            temp.append((element, 1))\n",
    "        temp.sort(key=lambda t: t[0])\n",
    "        ans = pow(10, 13) \n",
    "        pre_pair = temp[0]\n",
    "        for pair in temp[1:]:\n",
    "            if pre_pair[1] != pair[1]:\n",
    "                ans = min(ans, pair[0] - pre_pair[0])\n",
    "            pre_pair = pair[:]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        c = a[:] + b[:]\n",
    "        a = set(a)\n",
    "        b = set(b) \n",
    "        c = sorted(c)\n",
    "        res = float('inf')\n",
    "        for i in range(1, len(c)):\n",
    "            if (c[i] in a and c[i-1] in b) or (c[i-1] in a and c[i] in b):\n",
    "                res = min(res, abs(c[i] - c[i-1]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        c = a[:] + b[:]\n",
    "        a = set(a)\n",
    "        b = set(b) \n",
    "        c = sorted(c)\n",
    "        res = float('inf')\n",
    "        for i in range(1, len(c)):\n",
    "            if (c[i] in a and c[i-1] in b) or (c[i-1] in a and c[i] in b):\n",
    "                res = min(res, abs(c[i] - c[i-1]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        nums=[[i,0] for i in a]+[[i,1] for i in b]\n",
    "        nums=sorted(nums,key=lambda x:x[0])\n",
    "        ans=float(\"inf\")\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i][1] ^ nums[i-1][1]:\n",
    "                ans=min(abs(nums[i][0]-nums[i-1][0]),ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        C = list(zip(a,['a']*len(a))) + list(zip(b,['b']*len(b)))\n",
    "        C.sort()\n",
    "        res , tmp = 2147483647 , ''\n",
    "        for x in C:\n",
    "            if not tmp or x[1] == tmp[1]:\n",
    "                tmp = x\n",
    "            else:\n",
    "                res = min(res,x[0]-tmp[0])\n",
    "                if res == 0:\n",
    "                    return 0\n",
    "                else:\n",
    "                    tmp = x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        arr = []\n",
    "        left = 0\n",
    "        right = 0\n",
    "        a.sort()\n",
    "        b.sort()\n",
    "        while left<len(a) and right<len(b):\n",
    "            if a[left]<b[right]:\n",
    "                arr.append([a[left],-1])\n",
    "                left+=1\n",
    "            elif a[left]>b[right]:\n",
    "                arr.append([b[right],1])\n",
    "                right+=1\n",
    "            else:\n",
    "                return 0\n",
    "        while left<len(a):\n",
    "            arr.append([a[left],-1])\n",
    "            left+=1\n",
    "        while right<len(b):\n",
    "            arr.append([b[right],1])\n",
    "            right+=1\n",
    "        ans = 2147483647*2\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i-1][1]+arr[i][1] == 0:\n",
    "                ans = min(ans,arr[i][0]-arr[i-1][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: list[int], b: list[int]) -> int:\n",
    "        if len(a) == 0 or len(b) == 0:\n",
    "            raise \"Invalid Input\"\n",
    "        # element: tuple[value, value_from_a_list]\n",
    "        a_and_b: list[tuple[int, bool]] = ([(val, True) for val in a] +\n",
    "                                           [(val, False) for val in b])\n",
    "        a_and_b.sort()\n",
    "        min_distance: int | float = float(\"inf\")\n",
    "        for i in range(1, len(a_and_b)):\n",
    "            if a_and_b[i][1] == a_and_b[i-1][1]:\n",
    "                continue\n",
    "            else:\n",
    "                distance = a_and_b[i][0] - a_and_b[i-1][0]\n",
    "                min_distance = min(min_distance, distance)\n",
    "\n",
    "        return min_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        if set(a)&set(b):\n",
    "            return 0\n",
    "        b.sort()\n",
    "        res=(1<<33)\n",
    "        n=len(b)\n",
    "        for num in a:\n",
    "            x=bisect_right(b,num)\n",
    "            y=bisect_left(b,num)\n",
    "            if x==n:\n",
    "                res=min(res,num-b[-1])\n",
    "            elif y==0:\n",
    "                res=min(res,b[0]-num)\n",
    "            else:\n",
    "                res=min(res,b[x]-num,num-b[y-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        c=[]\n",
    "        for i in range(0,len(a)):\n",
    "            c.append((a[i],1))\n",
    "        for i in range(0,len(b)):\n",
    "            c.append((b[i],2))\n",
    "        c.sort(key=(lambda x:x[0]))\n",
    "        m=2147483648\n",
    "        for i in range(0,len(a)+len(b)-1):\n",
    "            if c[i+1][1]!=c[i][1]:\n",
    "                m=min(m,c[i+1][0]-c[i][0])\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        merge_list = a + b\n",
    "        merge_list.sort()\n",
    "        a_set = set(a)\n",
    "        b_set = set(b)\n",
    "        min_val = float(\"inf\")\n",
    "        for i in range(1, len(merge_list)):\n",
    "            if (abs(merge_list[i] - merge_list[i-1]) < min_val) and ((merge_list[i] in a_set and merge_list[i-1] in b_set) or merge_list[i-1] in a_set and merge_list[i] in b_set):\n",
    "                min_val = abs(merge_list[i] - merge_list[i-1])\n",
    "\n",
    "        return min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a_set = set(a)\n",
    "        b_set = set(b)\n",
    "        c = a + b\n",
    "        c.sort()\n",
    "\n",
    "        offset = abs(a[0] - b[0])\n",
    "        for i in range(len(c) - 1):\n",
    "            curr_n = c[i]\n",
    "            next_n = c[i + 1]\n",
    "            if (curr_n in a_set and next_n in b_set) or (curr_n in b_set and next_n in a_set):\n",
    "                offset = min(offset, next_n - curr_n)\n",
    "\n",
    "        return offset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        arr = []\n",
    "        for aa in a:\n",
    "            arr.append([aa,1])\n",
    "        for bb in b:\n",
    "            arr.append([bb,2])\n",
    "        arr.sort()\n",
    "        #print(arr)\n",
    "        ret = float('inf')\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i][1]!=arr[i-1][1]:\n",
    "                tmp = arr[i][0]-arr[i-1][0]\n",
    "                ret = min(tmp,ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        #动态规划\n",
    "        nums=[]\n",
    "        for i in a:\n",
    "            nums.append((i,'a'))\n",
    "        for j in b:\n",
    "            nums.append((j,'b'))\n",
    "        nums=sorted(nums,key=lambda x:x[0])\n",
    "        start=nums[0][1]\n",
    "        res=2**31\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i][1]!=start:\n",
    "                res=min(res,abs(nums[i-1][0]-nums[i][0]))\n",
    "                start=nums[i][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a1 = [(num,1) for num in a]\n",
    "        b1 = [(num,2) for num in b]\n",
    "        x = sorted(a1+b1)\n",
    "        return min([x[i][0]-x[i-1][0] if x[i][1]!=x[i-1][1] else 2147483647 for i in range(1,len(x))])\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        nums = [(num,1) for num in a] + [(num,2) for num in b]\n",
    "        nums.sort()\n",
    "        return min(nums[i+1][0]-nums[i][0] for i in range(len(nums)-1) if nums[i+1][1] != nums[i][1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        aa = [[i, 1] for i in a]\n",
    "        bb = [[i, 2] for i in b]\n",
    "        c = sorted(aa+bb)\n",
    "        return min([c[i+1][0] - c[i][0] if c[i+1][1] != c[i][1] else 2147483647 for i in range(len(c)-1)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "\n",
    "        c = a + b\n",
    "        c.sort()\n",
    "        ca, cb = Counter(a), Counter(b)\n",
    "\n",
    "        min1 = float('inf')\n",
    "        for i in range(len(c) - 1):\n",
    "            if (c[i + 1] in ca and c[i] in cb) or (c[i] in ca and c[i + 1] in cb): \n",
    "                min1 = min(c[i + 1] - c[i], min1)\n",
    "                if min1 == 0:\n",
    "                    return min1\n",
    "        return min1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "\n",
    "        c = a + b\n",
    "        c.sort()\n",
    "        ca, cb = Counter(a), Counter(b)\n",
    "\n",
    "        min1 = float('inf')\n",
    "        for i in range(len(c) - 1):\n",
    "            if (c[i + 1] in ca and c[i] in cb) or (c[i] in ca and c[i + 1] in cb): \n",
    "                min1 = min(c[i + 1] - c[i], min1)\n",
    "                if min1 == 0:\n",
    "                    return min1\n",
    "        return min1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a, b = [[i, 1] for i in a], [[i, 2] for i in b]\n",
    "        a = sorted(a+b)\n",
    "        return min([a[i+1][0] - a[i][0] if a[i+1][1] - a[i][1] != 0 else 2147483647 for i in range(len(a)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a, b = [[i, 1] for i in a], [[i, 2] for i in b]\n",
    "        a = sorted(a+b)\n",
    "        return min([a[i+1][0] - a[i][0] if a[i+1][1] - a[i][1] != 0 else 2147483647 for i in range(len(a)-1)])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        def merge_sort(arr):\n",
    "            tmp=[0]*len(arr)\n",
    "            def merge(arr,l,r):\n",
    "                if l>=r:return\n",
    "                m=(l+r)>>1\n",
    "                merge(arr,l,m)\n",
    "                merge(arr,m+1,r)\n",
    "                \n",
    "                tmp[l:r+1] = arr[l:r+1]\n",
    "                i,j=l,m+1\n",
    "                for k in range(l,r+1):\n",
    "                    if i==m+1:\n",
    "                        arr[k] = tmp[j]\n",
    "                        j+=1\n",
    "                    elif j==r+1 or tmp[i]<=tmp[j]:\n",
    "                        arr[k]=tmp[i]\n",
    "                        i+=1\n",
    "                    else:\n",
    "                        arr[k]=tmp[j]\n",
    "                        j+=1\n",
    "            merge(arr,0,len(arr)-1)\n",
    "            return arr\n",
    "        merge_sort(a)\n",
    "        merge_sort(b)\n",
    "        i=0\n",
    "        j=0\n",
    "        abs_min=float('inf')\n",
    "        # print(a,b)\n",
    "        while i<=len(a)-1 and j<=len(b)-1:\n",
    "            abs_min=abs(a[i]-b[j]) if (  abs(a[i]-b[j])<abs_min ) else abs_min\n",
    "            if a[i]<=b[j]:\n",
    "                i+=1\n",
    "            else:\n",
    "                 j+=1\n",
    "\n",
    "\n",
    "        return abs_min\n",
    "\n",
    "\n",
    " \n",
    "\n",
    "\n",
    "                        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a = [[x, 0] for x in a]\n",
    "        b = [[x, 1] for x in b]\n",
    "        temp = a + b\n",
    "        temp.sort(key = lambda x:x[0])\n",
    "        ans = float('inf')\n",
    "        for i in range(1, len(temp)):\n",
    "            if temp[i][0]-temp[i-1][0] < ans and temp[i][1] != temp[i-1][1]:\n",
    "                ans = temp[i][0]-temp[i-1][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        seq = [(i, 0) for i in a] + [(j, 1) for j in b]\n",
    "        seq.sort(key=lambda x:x[0])\n",
    "        print(seq)\n",
    "        res = float('inf')\n",
    "        cur = 0 # index start\n",
    "        while True:\n",
    "            v = seq[cur][0]\n",
    "            color = seq[cur][1]\n",
    "            b = cur + 1\n",
    "            while seq[b][1]==color and b<len(seq)-1:\n",
    "                b += 1\n",
    "            if b==len(seq)-1: # arrived end\n",
    "                if seq[b][1]!=color: # last try update min value \n",
    "                    res = min(res, seq[b][0]-seq[b-1][0])\n",
    "                return res \n",
    "            # now seq[b] have different color\n",
    "            res = min(res, seq[b][0]-seq[b-1][0])\n",
    "            cur = b\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        ab = []\n",
    "        for ai in a:\n",
    "            ab.append([ai, 1])\n",
    "        for bi in b:\n",
    "            ab.append([bi, -1])\n",
    "        ab = sorted(ab, key = lambda x:x[0])\n",
    "        re = -1\n",
    "        lasti = -1\n",
    "        for i in range(1, len(ab)):\n",
    "            if ab[i][1] != ab[i-1][1]:\n",
    "                lasti = i-1\n",
    "            if lasti < 0:\n",
    "                continue\n",
    "            res = abs(ab[i][0]-ab[lasti][0])\n",
    "            if re == -1:\n",
    "                re = res\n",
    "            else:\n",
    "                re = min(re, res)\n",
    "        return re\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        ab = []\n",
    "        for ai in a:\n",
    "            ab.append([ai, 1])\n",
    "        for bi in b:\n",
    "            ab.append([bi, -1])\n",
    "        ab = sorted(ab, key = lambda x:x[0])\n",
    "        re = -1\n",
    "        lasti = -1\n",
    "        for i in range(1, len(ab)):\n",
    "            if ab[i][1] != ab[i-1][1]:\n",
    "                lasti = i-1\n",
    "                res = abs(ab[i][0]-ab[lasti][0])\n",
    "                if re == -1:\n",
    "                    re = res\n",
    "                else:\n",
    "                    re = min(re, res)\n",
    "            if lasti < 0:\n",
    "                continue\n",
    "            \n",
    "        return re\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a, b = [[i, 1] for i in a], [[i, 2] for i in b]\n",
    "        a = sorted(a + b)\n",
    "        return min([a[i + 1][0] - a[i][0] if a[i + 1][1] - a[i][1] != 0 else 2147483647 for i in range(len(a) - 1)])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(len(a)):\n",
    "            a[i] = (a[i],0)\n",
    "        for i in range(len(b)):\n",
    "            b[i] = (b[i],1)    \n",
    "        c = a + b\n",
    "        c.sort(key=lambda x: x[0])\n",
    "        for i in range(len(c)-1):\n",
    "            if c[i][1] != c[i+1][1]:\n",
    "                ans = min(abs(c[i][0] - c[i+1][0]), ans )\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        lis1 = [[i, 1] for i in a]\n",
    "        lis2 = [[i, 2] for i in b]\n",
    "        lis = lis1 + lis2\n",
    "        lis.sort()\n",
    "\n",
    "        dist = 2**32\n",
    "        for i in range(1, len(lis)):\n",
    "            if lis[i][0] - lis[i-1][0] < dist and lis[i][1]!=lis[i-1][1]:\n",
    "                dist = lis[i][0] - lis[i-1][0]\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# @typingMonkey\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        d = {**dict.fromkeys(a, 0), **dict.fromkeys(b, 1)}\n",
    "        if len(d) < len(a) + len(b):\n",
    "            return 0\n",
    "        c = sorted(d)\n",
    "        return min((abs(c[i] - x) for i, x in enumerate(c[1: ]) if d[c[i]] ^ d[x]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        d = {**dict.fromkeys(a, 0), **dict.fromkeys(b, 1)}\n",
    "        if len(d) < len(a) + len(b):\n",
    "            return 0\n",
    "        c = sorted(d)\n",
    "        return min((abs(c[i] - x) for i, x in enumerate(c[1: ]) if d[c[i]] ^ d[x]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# @typingMonkey\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        d = {**dict.fromkeys(a, 0), **dict.fromkeys(b, 1)}\n",
    "        if len(d) < len(a) + len(b):\n",
    "            return 0\n",
    "        c = sorted(d)\n",
    "        return min((abs(c[i] - x) for i, x in enumerate(c[1: ]) if d[c[i]] ^ d[x]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        def cmp(a, b):\n",
    "            return a[0] - b[0]\n",
    "\n",
    "        a = [[v, 0] for v in a]\n",
    "        for v in b:\n",
    "            a.append([v, 1])\n",
    "        a = sorted(a, key=functools.cmp_to_key(cmp))\n",
    "        i, j = 0, 0\n",
    "        min_val = float('inf')\n",
    "        while i < len(a):\n",
    "            while i + 1 < len(a) and a[i][1] == a[i + 1][1]: i += 1\n",
    "            if i + 1 < len(a) and abs(a[i][0] - a[i + 1][0]) < min_val:\n",
    "                min_val = abs(a[i][0] - a[i + 1][0])\n",
    "                if min_val == 0: return min_val\n",
    "            i += 1\n",
    "        return min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        if len(set(a)) + len(set(b)) != len(set(a) | set(b)):\n",
    "            return 0\n",
    "        a = sorted(list(a))\n",
    "        b = sorted(list(b))\n",
    "        a_tik = 0\n",
    "        b_tik = 0\n",
    "        a_ = a[a_tik]\n",
    "        b_ = b[b_tik]\n",
    "        min_num = abs(a_ - b_)\n",
    "        while 1:\n",
    "            try:\n",
    "                if a_ > b_:\n",
    "                    b_tik += 1\n",
    "                    b_ = b[b_tik]\n",
    "                else:\n",
    "                    a_tik += 1\n",
    "                    a_ = a[a_tik]\n",
    "                min_num = min(min_num, abs(a_ - b_))\n",
    "            except:\n",
    "                return min_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        if len(set(a)) + len(set(b)) != len(set(a) | set(b)):\n",
    "            return 0\n",
    "        a = sorted(list(a))\n",
    "        b = sorted(list(b))\n",
    "        a_tik = 0\n",
    "        b_tik = 0\n",
    "        a_ = a[a_tik]\n",
    "        b_ = b[b_tik]\n",
    "        min_num = abs(a_ - b_)\n",
    "        while 1:\n",
    "            try:\n",
    "                if a_ > b_:\n",
    "                    b_tik += 1\n",
    "                    b_ = b[b_tik]\n",
    "                else:\n",
    "                    a_tik += 1\n",
    "                    a_ = a[a_tik]\n",
    "                min_num = min(min_num, abs(a_ - b_))\n",
    "            except IndexError:\n",
    "                return min_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a, b = [[i, 1] for i in a], [[i, 2] for i in b]\n",
    "        a = sorted(a+b)\n",
    "        return min([a[i+1][0] - a[i][0] if a[i+1][1] - a[i][1] != 0 else 2147483647 for i in range(len(a)-1)])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a,b=[[i,1] for i in a],[[i,2] for i in b]\n",
    "        a=sorted(a+b)\n",
    "        return min([a[i+1][0]-a[i][0] if a[i+1][1]-a[i][1]!=0 else 2147483647 for i in range(len(a)-1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a, b = [[i, 1] for i in a], [[i, 2] for i in b]\n",
    "        a = sorted(a+b)\n",
    "        return min([a[i+1][0] - a[i][0] if a[i+1][1] - a[i][1] != 0 else float('inf') for i in range(len(a)-1)])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestDifference(self, a: List[int], b: List[int]) -> int:\n",
    "        a, b = [[i, 1] for i in a], [[i, 2] for i in b]\n",
    "        a = sorted(a+b)\n",
    "        return min([a[i+1][0] - a[i][0] if a[i+1][1] - a[i][1] != 0 else 2147483647 for i in range(len(a)-1)])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
